package com.cqs.leetcode.queue;

import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

import static com.cqs.leetcode.ds.ArraysUtils.formatInts;

/**
 * @author lixw
 * @date 2020/3/3 9:27
 */
public class SlidingWindowMaximum239 {


    static class Solution {
        public int[] maxSlidingWindow(final int[] nums, final int k) {
            if (nums == null || nums.length == 0) return nums;
            int[] result = new int[nums.length - k + 1];
            //储存index
            Deque<Integer> windows = new LinkedList<>();
            for (int i = 0; i < nums.length; i++) {
                //1.判断队首的元素是否滑出窗口外
                if (windows.size() > 0 && i - windows.getFirst() >= k) {
                    //滑出窗口
                    windows.pollFirst();
                }
                //2. 调整队列: 从队尾开始，逐个删除<=nums[i]的元素，直到遇到比自己大的元素或者队列为空
                // ==》 去掉不大于当前结点元素（这样的元素没有资格成为窗口最大值）
                //==> 可以保证队列元素一定是递减的： 初始化的时候队列为空，所以传递下来的话，队列一定是递减的
                while (windows.size() > 0 && nums[windows.getLast()] <= nums[i]) {
                    //从队尾方向操作
                    windows.pollLast();
                }
                //3.新进的元素
                windows.addLast(i);
                //4. 去除窗口最大值
                if (i >= k - 1) {
                    result[i - k + 1] = nums[windows.getFirst()];
                }
            }
            return result;
        }
    }


    public static void main(String[] args) {
        Map<int[], Integer> cases = new LinkedHashMap<>();
        cases.put(new int[]{1, 3, -1, -3, 5, 3, 4}, 3);
        cases.put(new int[]{1, 3, -1, -3, 5, 3, 6}, 3);
        Solution solution = new Solution();
        cases.forEach((nums, k) -> {
            int[] result = solution.maxSlidingWindow(nums, k);
            System.out.println(formatInts(nums) + "\t k:" + k + "\t result:" + formatInts(result));
        });
    }
}
